/*
 *  linux/kernel/sched.c
 *
 *  (C) 1991  Linus Torvalds
 */

/*
 * 'sched.c' is the main kernel file. It contains scheduling primitives
 * (sleep_on, wakeup, schedule etc) as well as a number of simple system
 * call functions (type getpid(), which just extracts a field from
 * current-task
 */
#include "../include/linux/sched.h"
#include "../include/linux/kernel.h"
#include "../include/linux/sys.h"
#include "../include/linux/fdreg.h"
#include "../include/asm/system.h"
#include "../include/asm/io.h"
#include "../include/asm/segment.h"

#define _S(nr) (1<<((nr)-1))
#define _BLOCKABLE (~(_S(SIGKILL) | _S(SIGSTOP)))

void show_task(int nr,struct task_struct * p)
{
    int i,j = 4096-sizeof(struct task_struct);

    printk("%d: pid=%d, state=%d, father=%d, child=%d, ",nr,p->pid,
           p->state, p->p_pptr->pid, p->p_cptr ? p->p_cptr->pid : -1);
    i=0;
    while (i<j && !((char *)(p+1))[i])
        i++;
    printk("%d/%d chars free in kstack\n\r",i,j);
    printk("   PC=%08X.", *(1019 + (unsigned long *) p));
    if (p->p_ysptr || p->p_osptr)
        printk("   Younger sib=%d, older sib=%d\n\r",
               p->p_ysptr ? p->p_ysptr->pid : -1,
               p->p_osptr ? p->p_osptr->pid : -1);
    else
        printk("\n\r");
}

void show_state(void)
{
    int i;

    printk("\rTask-info:\n\r");
    for (i=0;i<NR_TASKS;i++)
        if (task[i])
            show_task(i,task[i]);
}

#define LATCH (1193180/HZ)

extern void mem_use(void);

extern int timer_interrupt(void);

extern int system_call(void);

union task_union {
    struct task_struct task;
    char stack[PAGE_SIZE];
};

static union task_union init_task = {INIT_TASK,};

unsigned long volatile jiffies=0;
unsigned long startup_time=0;
int jiffies_offset = 0;		/* # clock ticks to add to get "true
				   time".  Should always be less than
				   1 second's worth.  For time fanatics
				   who like to syncronize their machines
				   to WWV :-) */
struct task_struct *current = &(init_task.task);
struct task_struct *last_task_used_math = NULL;

struct task_struct *task[NR_TASKS] = {&(init_task.task),};

long user_stack[PAGE_SIZE >> 2];

struct {
    long *a;
    short b;
} stack_start = {&user_stack[PAGE_SIZE >> 2], 0x10};

/*
 *  'math_state_restore()' saves the current math information in the
 * old math state array, and gets the new ones from the current task
 */
void math_state_restore() {
    if (last_task_used_math == current)
        return;
    __asm__("fwait");
    if (last_task_used_math) {
        __asm__("fnsave %0"::"m" (last_task_used_math->tss.i387));
    }
    last_task_used_math = current;
    if (current->used_math) {
        __asm__("frstor %0"::"m" (current->tss.i387));
    } else {
        __asm__("fninit"::);
        current->used_math = 1;
    }
}

/*
 *  'schedule()' is the scheduler function. This is GOOD CODE! There
 * probably won't be any reason to change this, as it should work well
 * in all circumstances (ie gives IO-bound processes good response etc).
 * The one thing you might take a look at is the signal-handler code here.
 *
 *   NOTE!!  Task 0 is the 'idle' task, which gets called when no other
 * tasks can run. It can not be killed, and it cannot sleep. The 'state'
 * information in task[0] is never used.
 */
void schedule(void) {
    int i, next, c;
    struct task_struct **p;

/* check alarm, wake up any interruptible tasks that have got a signal */

    for (p = &LAST_TASK; p > &FIRST_TASK; --p)
        if (*p) {
            if ((*p)->timeout && (*p)->timeout < jiffies) {
                (*p)->timeout = 0;
                if ((*p)->state == TASK_INTERRUPTIBLE)
                    (*p)->state = TASK_RUNNING;
            }
            //设置过任务的定时值alarm 并且 系统的滴答值已经超过定时值
            if ((*p)->alarm && (*p)->alarm < jiffies) {
                // 设置signal 对应二进制位 为1
                (*p)->signal |= (1 << (SIGALRM - 1));
                (*p)->alarm = 0;
            }
            //~(_BLOCKABLE & (*p)->blocked)
            // _BLOCKABLE为可以阻塞的信号集合，blocked为当前进程设置的阻塞集合
            // & 进程中被阻塞的信号集合， ~ 表示可以接受的信号集合
            if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
                (*p)->state == TASK_INTERRUPTIBLE)
                (*p)->state = TASK_RUNNING;
        }

/* this is the scheduler proper: */

    while (1) {
        c = -1;
        next = 0;
        i = NR_TASKS;
        p = &task[NR_TASKS];
        // 从最后一个进程任务开始，找出(*p)->counter最大的任务号，赋给next
        while (--i) {
            if (!*--p)
                continue;
            if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
                c = (*p)->counter, next = i;
        }
        //找到了，退出循环
        if (c) break;
        //没有找到，所有进程的counter都为0，重新设置所有进程的counter
        for (p = &LAST_TASK; p > &FIRST_TASK; --p)
            if (*p)
                (*p)->counter = ((*p)->counter >> 1) +
                                (*p)->priority;
    }
    switch_to(next);
}

int sys_pause(void) {
    current->state = TASK_INTERRUPTIBLE;
    schedule();
    return 0;
}


// 把当前任务置为不可中断的等待状态，并让睡眠队列头指针指向当前任务。
// 只有明确地唤醒(wake_up)才会返回。该函数提供了进程与中断处理程序之间的同步机制。
// 函数参数，是等待任务队列头指针。
// 指针是含有一个变量地址的交量。这里参数p使用了指针的指针形式’**p’，这是因为C函数参数只能传值，没有直接的方式让被调用函数改变调用该函数程序中变量的值。
// 但是指针’*’指向的目标（这里是任务结构）会改变，因此为了能修改调用该函数程序中原来就是指针变量的值，就需要传递指针’*p’的指针，即’**p’。
static inline void __sleep_on(struct task_struct **p, int state)
{
    struct task_struct *tmp;
    // 若指针无效，则退出。（指针所指的对象可以是 NUL，但指针本身不应该为0）。
    // 另外，如果 当前任务是任务0，则死机。因为任务0 的运行不依赖自己的状态，所以内核代码把任务0置为睡眠状态毫无意义。
    if (!p)
        return;
    if (current == &(init_task.task))
        panic("task[0] trying to sleep");
    tmp = *p;
    *p = current;
    current->state = state;
    repeat:	schedule();

    // 只有当这个等待任务被唤醒时，调度程序才又返回到这里，表示本进程已被明确地唤醒（就绪态）。
    // 例如：ABC 三个进程，A、B、C 三个进程都在等待同一个资源，
    // 进程A中调用  sleep_on(&wait_queue);  tmp = null, *p(也就是&wait_queue） = A
    // 进程B中调用  sleep_on(&wait_queue);  tmp = A,    *p(也就是&wait_queue） = B
    // 进程C中调用  sleep_on(&wait_queue);  tmp = B,    *p(也就是&wait_queue） = C
    //
    // 于是在进程C中调用wake_up(&wait_queue); 时，
    // 把C唤醒了，执行tmp->state = 0，这里的tmp就是B
    // 把B唤醒了，执行tmp->state = 0，这里的tmp就是A
    // 把A唤醒了，tmp = null
    if (*p && *p != current) {
        (**p).state = 0;
        current->state = TASK_UNINTERRUPTIBLE;
        goto repeat;
    }
    if (!*p)
        printk("Warning: *P = NULL\n\r");
    if (*p = tmp)
        tmp->state=0;
}



void interruptible_sleep_on(struct task_struct **p)
{
    __sleep_on(p,TASK_INTERRUPTIBLE);
}

void sleep_on(struct task_struct **p)
{
    __sleep_on(p,TASK_UNINTERRUPTIBLE);
}

void wake_up(struct task_struct **p)
{
    if (p && *p) {
        if ((**p).state == TASK_STOPPED)
            printk("wake_up: TASK_STOPPED");
        if ((**p).state == TASK_ZOMBIE)
            printk("wake_up: TASK_ZOMBIE");
        (**p).state=0;
    }
}

/*
 * OK, here are some floppy things that shouldn't be in the kernel
 * proper. They are here because the floppy needs a timer, and this
 * was the easiest way of doing it.
 */
static struct task_struct *wait_motor[4] = {NULL, NULL, NULL, NULL};
static int mon_timer[4] = {0, 0, 0, 0};
static int moff_timer[4] = {0, 0, 0, 0};
unsigned char current_DOR = 0x0C;

int ticks_to_floppy_on(unsigned int nr) {
    extern unsigned char selected;
    unsigned char mask = 0x10 << nr;

    if (nr > 3)
        panic("floppy_on: nr>3");
    moff_timer[nr] = 10000;        /* 100 s = very big :-) */
    cli();                /* use floppy_off to turn it off */
    mask |= current_DOR;
    if (!selected) {
        mask &= 0xFC;
        mask |= nr;
    }
    if (mask != current_DOR) {
        outb(mask, FD_DOR);
        if ((mask ^ current_DOR) & 0xf0)
            mon_timer[nr] = HZ / 2;
        else if (mon_timer[nr] < 2)
            mon_timer[nr] = 2;
        current_DOR = mask;
    }
    sti();
    return mon_timer[nr];
}

void floppy_on(unsigned int nr) {
    cli();
    while (ticks_to_floppy_on(nr))
        sleep_on(nr + wait_motor);
    sti();
}

void floppy_off(unsigned int nr) {
    moff_timer[nr] = 3 * HZ;
}

void do_floppy_timer(void) {
    int i;
    unsigned char mask = 0x10;

    for (i = 0; i < 4; i++, mask <<= 1) {
        if (!(mask & current_DOR))
            continue;
        if (mon_timer[i]) {
            if (!--mon_timer[i])
                wake_up(i + wait_motor);
        } else if (!moff_timer[i]) {
            current_DOR &= ~mask;
            outb(current_DOR, FD_DOR);
        } else
            moff_timer[i]--;
    }
}

#define TIME_REQUESTS 64

static struct timer_list {
    long jiffies;

    void (*fn)();

    struct timer_list *next;
} timer_list[TIME_REQUESTS], *next_timer = NULL;

void add_timer(long jiffies, void (*fn)(void)) {
    struct timer_list *p;

    if (!fn)
        return;
    cli();
    if (jiffies <= 0)
        (fn)();
    else {
        for (p = timer_list; p < timer_list + TIME_REQUESTS; p++)
            if (!p->fn)
                break;
        if (p >= timer_list + TIME_REQUESTS)
            panic("No more time requests free");
        p->fn = fn;
        p->jiffies = jiffies;
        p->next = next_timer;
        next_timer = p;
        while (p->next && p->next->jiffies < p->jiffies) {
            p->jiffies -= p->next->jiffies;
            fn = p->fn;
            p->fn = p->next->fn;
            p->next->fn = fn;
            jiffies = p->jiffies;
            p->jiffies = p->next->jiffies;
            p->next->jiffies = jiffies;
            p = p->next;
        }
    }
    sti();
}

void do_timer(long cpl) {
    static int blanked = 0;

    if (blankcount || !blankinterval) {
        if (blanked)
            unblank_screen();
        if (blankcount)
            blankcount--;
        blanked = 0;
    } else if (!blanked) {
        blank_screen();
        blanked = 1;
    }
    if (hd_timeout)
        if (!--hd_timeout)
            hd_times_out();

    if (beepcount)
        if (!--beepcount)
            sysbeepstop();

    if (cpl)
        current->utime++;
    else
        current->stime++;

    if (next_timer) {
        next_timer->jiffies--;
        while (next_timer && next_timer->jiffies <= 0) {
            void (*fn)(void);

            fn = next_timer->fn;
            next_timer->fn = NULL;
            next_timer = next_timer->next;
            (fn)();
        }
    }
    if (current_DOR & 0xf0)
        do_floppy_timer();
    if ((--current->counter) > 0) return;
    current->counter = 0;
    if (!cpl) return;
    schedule();
}

int sys_alarm(long seconds) {
    int old = current->alarm;

    if (old)
        old = (old - jiffies) / HZ;
    current->alarm = (seconds > 0) ? (jiffies + HZ * seconds) : 0;
    return (old);
}

int sys_getpid(void) {
    return current->pid;
}

int sys_getppid(void) {
    return current->p_pptr->pid;
}

int sys_getuid(void) {
    return current->uid;
}

int sys_geteuid(void) {
    return current->euid;
}

int sys_getgid(void) {
    return current->gid;
}

int sys_getegid(void) {
    return current->egid;
}

int sys_nice(long increment) {
    if (current->priority - increment > 0)
        current->priority -= increment;
    return 0;
}

void sched_init(void) {
    int i;
    //用于表示一个描述符
    struct desc_struct *p;

    if (sizeof(struct sigaction) != 16)
        panic("Struct sigaction MUST be 16 bytes");

    //使用 set_tss_desc 和 set_ldt_desc 函数设置任务状态段（TSS）和局部描述符表（LDT）的描述符。
    set_tss_desc(gdt + FIRST_TSS_ENTRY, &(init_task.task.tss));

    //{0x00c0fa00 0000009f}, 第一个任务0的ldt[1] 代码段
    // 0x00c0fa00 = 0000 0000 1100 0000 1111 1010 0000 0000
    // G=1,D=1, 内存段颗粒度为4Kb, 默认操作数为32位。
    // P=1(有效), S=1(代码或数据), DPL=11（特权级3）
    // TYPE=1010=1CRA (C=0,A=0,R=1(可读));
    // 0x0000009f 表示段限长，159个4KB，不超过160个4KB = 640K
    // 0K~640K 是操作系统可用的全部物理内存空间，超过640K的物理内存用于一些缓存和高速缓冲区，
    // 1M以下的物理内存分布，是计划好的。详解bootsect.s的内存分布
    //
    //{0x00c0f200 0000009f}, 第一个任务0的ldt[2] 数据段
    // 0x00c0f200 = 0000 0000 1100 0000 1111 0010 0000 0000
    // G=1,D=1, 内存段颗粒度为4Kb, 默认操作数为32位。
    // P=1(有效), S=1(代码或数据), DPL=11（特权级3）
    // TYPE=0010=0EWA (W=1(可写数据内存段), E=A=0;);
    set_ldt_desc(gdt + FIRST_LDT_ENTRY, &(init_task.task.ldt));
    //指向GDT表的末端
    p = gdt + 2 + FIRST_TSS_ENTRY;
    for (i = 1; i < NR_TASKS; i++) {
        task[i] = NULL;
        //将 GDT 中对应的 TSS 描述符清零。
        p->a = p->b = 0;
        p++;
        //将 GDT 中对应的 LDT 描述符清零。
        p->a = p->b = 0;
        p++;
    }
/* Clear NT, so that we won't have troubles with that later on */
    __asm__("pushfl ; andl $0xffffbfff,(%esp) ; popfl");
    ltr(0);
    lldt(0);
    //通过 outb_p 函数向 8253 定时器芯片发送初始化命令，这样设置是为了定时器芯片能定时产生中断给cpu
    outb_p(0x36, 0x43);        /* binary, mode 3, LSB/MSB, ch 0 */
    outb_p(LATCH & 0xff, 0x40);    /* LSB */
    outb(LATCH >> 8, 0x40);    /* MSB */
    // 设置了中断处理函数 timer_interrupt。
    set_intr_gate(0x20, &timer_interrupt);

    //屏蔽主 8259A 芯片上的 IRQ0，并设置系统调用中断处理程序。
    outb(inb_p(0x21) & ~0x01, 0x21);
    set_system_gate(0x80, &system_call);
}